package com.lfg.leetcode.leetcode200;

import java.util.*;

public class No218getSkyline {

    public static void main(String[] args) {
//        int[][] buildings = new int[][]{
//                new int[]{2, 9, 10},
//                new int[]{3, 7, 15},
//                new int[]{5, 12, 12},
//                new int[]{15, 20, 10},
//                new int[]{19, 24, 8}
//        };
        int[][] buildings = new int[][]{
                new int[]{0, 2, 3},
                new int[]{2, 5, 3}
        };
        List<int[]> ret = getSkyline(buildings);
        System.out.println(ret);
    }

    public static List<int[]> getSkyline(int[][] buildings) {
        List<int[]> ret = new ArrayList<>();
        if (buildings.length == 0) {
            return ret;
        }
        List<int[]> data = new ArrayList<>(buildings.length * 2);
        for (int i = 0; i < buildings.length; i++) {
            data.add(new int[]{buildings[i][0], buildings[i][2]});
            data.add(new int[]{buildings[i][1], -buildings[i][2]});
        }
        Collections.sort(data, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return o2[1] - o1[1];
                }
                return o1[0] - o2[0];
            }
        });

        Queue<Integer> pq = new PriorityQueue<Integer>(11, new Comparator<Integer>() {
            @Override
            public int compare(Integer i1, Integer i2) {
                return i2 - i1;
            }
        });
        pq.offer(0);
        int preHeight = 0;
        for (int[] array : data) {
            if (array[1] > 0) {
                pq.add(array[1]);
            } else {
                pq.remove(-array[1]);
            }
            int height = pq.peek();
            if (preHeight != height) {
                ret.add(new int[]{array[0], height});
                preHeight = height;
            }
        }
        return ret;
    }
}
